#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
		int len = s.size();
		if(len == 1) return s;
		int realLeft = 0, realRight = 0;
		for(int i = 0; i < len; i++){
			for(int j = len - 1; j > i; j--){
				if(s[i] != s[j]){
					continue;
				}else{
					if((j - i > realRight - realLeft) && isPalindrome(s, i, j)){
						realRight = j;
						realLeft = i;
						break;
					}
				}
			}
		}
		return s.substr(realLeft, realRight - realLeft + 1);
    }
	
	bool isPalindrome(string s, int left, int right){
		while(left < right){
			if(s[left] == s[right]){
				left++;
				right--;
			}else{
				return false;
			}
		}
		return true;
	}
	
	string longestPalindrome1(string s) {
		int n=s.size();
        if(n==1)    return s;
        vector<vector<int>> dp(n,vector<int>(n,false));
        for(int i=0;i<n;++i){
            dp[i][i]=true;
        }
        int maxLen = 1;
        int begin = 0;
        for(int i=n-1;i>=0;--i){
            for(int j=i+1;j<=n-1;++j){
                if(s[i]==s[j]){
                    if(j == i + 1){
                        dp[i][j]=true;
                    }
                    else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
	}
};

int main(){
	string s = "abcdabc";
	Solution so;
	string s1 = so.longestPalindrome(s);
	cout << s1 << endl;
	return 0;
}
